#define _CRT_SECURE_NO_WARNINGS 1
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<unordered_map>
#include<queue>
#include<stack>
#include <functional>
#include <memory>
using namespace std;

class Solution {
public:
    int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
        unordered_set<string> vist;
        unordered_set<string> hash(wordList.begin(), wordList.end());
        if (hash.count(endWord) == 0) return 0;
        if (beginWord == endWord) return 1;

        int ret = 0;
        queue<string> qt;
        qt.push(beginWord);
        vist.insert(beginWord);

        while (qt.size())
        {
            int num = qt.size();
            ret++;
            for (int i = 0; i < num; i++)
            {
                string s = qt.front();
                qt.pop();
                for (int j = 0; j < s.size(); j++)
                {
                    string tmp = s;
                    for (int k = 0; k < 26; k++)
                    {
                        tmp[j] = ('a' + k);
                        if (vist.count(tmp) == 0 && hash.count(tmp))
                        {
                            if (tmp == endWord) return ret + 1;
                            vist.insert(tmp);
                            qt.push(tmp);
                        }
                        tmp[j] = ('A' + k);
                        if (vist.count(tmp) == 0 && hash.count(tmp))
                        {
                            if (tmp == endWord) return ret + 1;
                            vist.insert(tmp);
                            qt.push(tmp);
                        }
                    }
                }
            }
        }
        return 0;
    }
};

int main()
{
	std::unique_ptr<Tmp> user = make_unique<Tmp>();
	return 0;
}